package com.动态规划.基础;

import java.util.ArrayList;
import java.util.List;

public class 斐波拉契数列 {

    //动态规划法
    public static int fib(int n) {
        List<Integer> dp=new ArrayList<Integer>();
        dp.add(0);
        dp.add(1);
        for(int i=2;i<=n;i++){
            dp.add(i,dp.get(i-1)+dp.get(i-2));
        }
        return dp.get(n);
    }
    //动态规划法优化
    public static int fib_improve(int n) {
        int a=0,b=1,c=0;
        if(n==0)  return 0;
        if(n==1) return 1;
        for (int i = 2; i <=n; i++) {
            c=a+b;
            a=b;
            b=c;
        }
        return c;

//        int[] dp=new int[2];
//        if(n==0)  return 0;
//        if(n==1) return 1;
//        dp[0]=0;
//        dp[1]=1;
//        int sum=0;
//        for (int i = 2; i <=n; i++) {
//            sum=dp[0]+dp[1];
//            dp[0]=dp[1];
//            dp[1]=sum;
//        }
//        return sum;
    }
    public static void main(String[] args) {
        System.out.println(fib(4));

    }
}
